// // https://www.lintcode.com/problem/word-search/description
// // 时间复杂度应该是： m * n * 4 ^ word.length
class Solution {
public:
    /**
     * @param board: A list of lists of character
     * @param word: A string
     * @return: A boolean
     */
    vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    bool isBounded(int x, int y, vector<vector<char>> &board) {
        int n = board.size();
        int m = board[0].size();
        return x >= 0 && x < n && y >= 0 && y < m;
    }
    bool dfs(vector<vector<char>>& board, int idx, string word, int x, int y,
        vector<vector<bool>>& visited) { //传引用！！！不然TLE
        if (idx == word.length()) {
            return true;
        }
        if (!isBounded(x, y, board)) {
            return false;
        }
        if (visited[x][y] || board[x][y] != word[idx]) {
            return false;
        }

        visited[x][y] = true; //visited直接对当前对操作，省得漏了
        for (int i = 0; i < 4; ++i) {
            int newx = x + dir[i][0];
            int newy = y + dir[i][1];
            if (dfs(board, idx + 1, word, newx, newy, visited)) {
                return true;
            }
        }
        visited[x][y] = false;

        return false;
    }
    bool exist(vector<vector<char>> &board, string &word) {
        int n = board.size();
        int m = board[0].size();
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (dfs(board, 0, word, i, j, visited))
                    return true;
            }
        }
        return false;
    }
};

// class Solution {
// public:
//     /**
//      * @param board: A list of lists of character
//      * @param word: A string
//      * @return: A boolean
//      */
//     bool exist(vector<vector<char>> &board, string &word) {
//         // write your code here
//         for(auto i=0u;i<board.size();++i)
//             for(auto j=0u;j<board[i].size();++j)
//                 if(board[i][j]==word.front()&&
//                     verify(board,word.c_str(),i,j))
//                     return true;
//         return false;
//     }
//     bool verify(vector<vector<char>> &board,const char*p,int i,int j){
//         if(!*p)
//             return true;
//         if(i<0||j<0||i>=board.size()||j>=board[i].size()||*p!=board[i][j])
//             return false;
//         board[i][j]='\0';
//         ++p;
//         auto result=verify(board,p,i+1,j)||
//                 verify(board,p,i-1,j)||
//                 verify(board,p,i,j+1)||
//                 verify(board,p,i,j-1);
//         board[i][j]=*--p;
//         return result;
//     }
// };